public class Solution134 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int i = 0;
        while (i < n) {
            int sum = 0;
            int cnt = i;
            int j = 0;
            while (j < n) {
                sum += gas[cnt % n] - cost[cnt % n];
                if (sum < 0) {
                    break;
                }
                cnt++;
                j++;
            }
            if (cnt == n) {
                return i;
            } else {
                i = cnt + 1;
            }
        }
        return -1;
    }
    /*思路复杂
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum = 0;
        for (int i = 0; i < gas.length; i++) {
            gas[i] -= cost[i];
            sum += gas[i];
            cost[i] = sum;
        }
        if (sum < 0) {
            return -1;
        }
        int res = gas.length - 1;
        while (gas[res] < 0) {  //从后往前找到第一个能剩开到下一个站的点
            res--;
        }
        //不断找到能到达点res的加油站，更新res
        for (int i = res - 1; i >= 0; i--) {
            while (i > 0 && (gas[i - 1] >= 0 || gas[i] < 0)) {
                i--;
            }
            if (cost[res - 1] - (i > 0 ? cost[i - 1] : 0) >= 0) {
                res = i;
            } else {
                break;
            }
        }
        return res;
    }*/
}
